\section{Modélisation formelle du problème}
\label{formal-modelisation}

Pour correctement analyser le problème et pouvoir le résoudre, il faut le modéliser formellement. Nous allons donc, dans cette section, écarter le contexte du problème initial, pour n'étudier que le c\oe{}ur de celui-ci, le formaliser, le découper et le résoudre. Dans l'analyse de la section précédente, nous avons déjà fait un parallèle entre le problème de la redistribution et un problème de coloration de graphe (tout comme l'était le problème de la distribution). Nous avons donc deux graphes, l'un associé à l'ancienne version du code du programme et l'autre associé à la nouvelle version du code. La solution recherchée est de trouver une coloration qui tient compte des deux critères, à savoir: (i) conserver au maximum la structure de distribution précédente, et (ii) minimiser les transmissions de messages entre les différents sites. \\

Comme ce problème est, au départ, assez conséquent, nous allons tout d'abord le diviser en sous-problèmes. Ensuite, comme nous faisons le rapprochement avec un problème de coloration de graphe, il va falloir définir les différents graphes sur lesquels nous allons travailler. Ensuite, il faudra décrire les deux coûts (de redistribution et de transmission) dans le cadre des graphes, puis nous allons modéliser les deux parties constituant le problème initial et en proposer des solutions. Enfin, nous terminerons par un exemple illustrant la méthode de redistribution et par une explication de l'implémentation de cette méthode.

\subsection{Division du problème initial en sous-problèmes}

Étant donné deux graphes, l'un étant une modification de l'autre (c'est-à-dire que l'on a effectué diverses opérations sur les n\oe{}uds et les arcs d'un des graphes), le problème faut trouver une coloration pour le \textit{nouveau} graphe en tenant compte des critères désirés. Il est possible d'identifier alors deux sous-problèmes: (i) la comparaison entre les deux graphes et (ii) la coloration optimale selon des critères. Détaillons ces deux sous-problèmes. \\

La comparaison de graphes va servir à identifier les n\oe{}uds du nouveau graphe qui n'ont pas été modifiés, c'est-à-dire qui sont présents sous la même \textit{forme} dans le premier graphe. Ceci signifie qu'ils contiennent les mêmes informations. C'est grâce à cette partie de problème que nous allons pouvoir tenter de conserver au maximum l'ancienne structure de distribution. En effet, si deux n\oe{}uds sont comparés et se correspondent, le n\oe{}ud se trouvant dans le nouveau graphe peut prendre la couleur qu'il avait dans le premier graphe. Le but de ce sous-problème, étant donné deux graphes $G_1 = (V_1, E_1)$ et $G_2 = (V_2, E_2)$, sera donc de trouver une fonction $M : V_1 \rightarrow V_2$ qui décrit les correspondances entre les n\oe{}uds des deux graphes. Cette fonction est évidemment partielle, puisque certains n\oe{}uds du nouveau graphe auront été ajoutés ou modifiés et ne peuvent donc pas être mis en correspondance avec des anciens n\oe{}uds. De même, certains n\oe{}uds du premier graphe auront été supprimés, ce qui implique qu'il ne peut pas y avoir leur équivalent dans le nouveau graphe. Dans la suite de ce travail, nous ferons référence à ce problème sous le nom de \textit{problème de comparaison}. \\

Le second sous-problème est, logiquement, la coloration des noeuds du nouveau graphe. C'est ici qu'il faudra réellement tenir compte des deux critères d'optimisation de la coloration: d'un côté, il faudra essayer de laisser la coloration réalisée par le premier problème, à l'aide de la fonction $M$, et de l'autre, il faudra essayer de finir la coloration pour qu'il y ait un minimum de transmissions. Il est donc clair que ce problème se base sur l'ensemble qui définit les contraintes de couleur imposées à certains n\oe{}uds ainsi que sur la fonction $M$ qui permet d'avoir une correspondance entre les n\oe{}uds des deux graphes. Il est important de garder à l'esprit qu'il est nécessaire d'avoir la fonction de correspondance $M$ donnée par le premier sous-problème pour pouvoir effectuer le second sous-problème. En effet, si cette fonction n'est pas utilisée, la coloration se fera sans réellement tenir compte du critère de conservation de l'ancienne structure de distribution. Dans la suite de ce travail, nous ferons référence à ce problème sous le nom de \textit{problème de re-coloration}.

\subsection{Définition du graphe et de ses propriétés}
\label{graph-definition}

Le problème initial est divisé en deux sous-problèmes qui utilisent des graphes. Nous allons définir un type de graphe pour chacun des deux sous-problèmes, puisqu'ils n'ont pas exactement besoin des mêmes informations. En effet, le premier sous-problème a seulement besoin d'un graphe qui représente la structure du code, avec les liens entre les instructions, tandis que le second sous-problème n'a besoin que de certains n\oe{}uds et des liens modélisant les transmissions qu'il peut y avoir. Voyons tout d'abord la description et les propriétés du graphe pour le problème de comparaison et, ensuite, l'explication et les propriétés du graphe pour le problème de re-coloration.

\subsubsection{Le graphe pour la comparaison de graphes}
Pour le premier sous-problème, nous l'avons dit, il nous faut le graphe représentant la structure du code, c'est-à-dire les liens qu'il peut y avoir entre des instructions. Ces liens imposent que les n\oe{}uds reliés soient de la même couleur, c'est-à-dire que le graphe contiendra des composantes connexes (parfois, il ne s'agira que d'un seul n\oe{}ud isolé) qui seront colorées d'une même couleur. De manière un peu plus formelle, la construction d'un tel graphe se fera de la manière suivante, à partir du code: \\

\begin{enumerate}
	\item Pour chaque instruction du programme, un n\oe{}ud est créé et ajouté dans l'ensemble des n\oe{}uds du graphe;
	\item Pour chaque variable $v$ utilisée dans les instructions $i$ et $i'$, un arc est créé entre les n\oe{}uds $i$ et $i'$;
	\item Pour chaque instruction $i'$ atteignable depuis $i$, un arc est créé entre les n\oe{}uds $i$ et $i'$. 
\end{enumerate}

\bigskip
\noindent
La définition d'une instruction $i'$ atteignable depuis une instruction $i$ est donnée en section~\ref{distrib-first-step}. Remarquez que, dans ce type de graphe, nous ne nous soucions pas des variables. En effet, les variables ne sont pas utiles et alourdissent le graphe et il sera toujours possible de connaître les variables du programme en inspectant les instructions. Remarquez également que, pour le problème de comparaison, un tel type de graphe doit être construit pour l'ancienne version du code ainsi que pour la nouvelle version du code puisqu'il faut comparer les deux graphes. De plus, les n\oe{}uds doivent avoir certains attributs contenant un maximum d'informations pour pouvoir les identifier de manière unique. Nous pouvons imaginer avoir les attributs suivants : \\

\begin{itemize}
	\item le label de l'instruction;
	\item l'ensemble des variables que l'instruction utilise;
	\item la \texttt{METHOD}, \texttt{SEQUENCE} ou le \texttt{WHEN} dans lequel l'instruction se trouve;
	\item la contrainte de couleur sur l'instruction (venant d'une des variables utilisées par l'instruction), si elle existe.
\end{itemize}

\bigskip
Voici un exemple de petit code et son graphe associé pour illustrer ce type de graphe. Le graphe et le code associé sont représentés en figure~\ref{compare_graph_ex} (par souci de lisibilité, les n\oe{}uds du graphe ont le numéro de ligne comme label). Sur cette figure, les arcs en gras sont les arcs qui relient les instructions qui utilisent la même variable, tandis que les arcs qui ne sont pas en gras relient les instructions qui sont atteignables. 

\begin{figure}[h]
	\begin{minipage}[b]{0.5\linewidth}
		\begin{alltt}
			01:  SEQUENCE MySequence()
			02:      a := a + 1;
			03:      b := b + 2;
			04:      c := c + 3;
			05:      IF (b == 30) THEN
			06:          b := 0;
			07:          d := TRUE;
			08:      END_IF
			09:  END_SEQUENCE
			10:  WHEN a == 100 THEN
			11:      b := b + 2;
			12:  END_WHEN
		\end{alltt}
	\end{minipage}
	\hspace{0.2cm}
	\begin{minipage}[b]{0.5\linewidth}
		\begin{center}
			\includegraphics[scale=0.35]{Images/compare_graph_ex.pdf}
		\end{center}
	\end{minipage}
	\caption{À gauche, le morceau de code de l'exemple; à droite, le graphe pour le problème de comparaison de ce morceau de code}
	\label{compare_graph_ex}
\end{figure}

Pour que l'exemple soit parfaitement complet, il faut encore donner les valeurs des attributs des différents n\oe{}uds. Ceux-ci sont donc donnés dans le tableau ci-dessous. Dans cet exemple, on peut voir que, même si les n\oe{}uds 3 et 11 ont le même code, grâce aux attributs, ceux-ci peuvent être différenciés. 

\begin{center}
	\begin{tabular}{|c|c|c|c|c|}
		\hline
		\textbf{N\oe{}ud n°} & \textbf{label} & \textbf{variables} & \textbf{position code} & \textbf{contrainte} \\
		\hline
		\hline
		2 & \texttt{a := a + 1} & $\lbrace$\texttt{a}$\rbrace$ & \texttt{SEQUENCE MySequence} & - \\
		\hline
		3 & \texttt{b := b + 2} & $\lbrace$\texttt{b}$\rbrace$ & \texttt{SEQUENCE MySequence} & - \\
		\hline
		4 & \texttt{c := c + 3} & $\lbrace$\texttt{c}$\rbrace$ & \texttt{SEQUENCE MySequence} & - \\
		\hline
		5 & \texttt{IF (b == 30) THEN} & $\lbrace$\texttt{b}$\rbrace$ & \texttt{SEQUENCE MySequence} & - \\
		\hline
		6 & \texttt{b := 0} & $\lbrace$\texttt{b}$\rbrace$ & \texttt{SEQUENCE MySequence} & - \\
		\hline
		7 & \texttt{d := TRUE} & $\lbrace$\texttt{d}$\rbrace$ & \texttt{SEQUENCE MySequence} & - \\
		\hline
		10 & \texttt{WHEN a == 100 THEN} & $\lbrace$\texttt{a}$\rbrace$ & \texttt{WHEN a == 100 THEN} & - \\
		\hline
		11 & \texttt{b := b + 2} & $\lbrace$\texttt{b}$\rbrace$ & \texttt{WHEN a == 100 THEN} & - \\
		\hline
	\end{tabular}
\end{center}

\subsubsection{Le graphe pour le problème de la re-coloration}
Il est question, dans ce problème, de trouver une nouvelle coloration basée sur l'ancienne et qui minimise le plus possible les transmissions sans modifier complètement la structure de distribution. À l'instar du graphe pour le problème de comparaison, il faut un graphe contenant des n\oe{}uds représentant les instructions, mais pas les variables (pour la même raison, à savoir que celles-ci alourdissent le graphe et que l'on peut toujours connaître les variables utilisées dans les instructions). Deux différences existent, cependant, entre le graphe pour la re-coloration et le graphe pour la comparaison. \\

La première, c'est qu'il ne faut considérer que les instructions séquentielles, c'est-à-dire les instructions qui se situent dans une \texttt{SEQUENCE}. En effet, il n'y a que les exécutions de ces instructions séquentielles qui ont besoin d'être synchronisées, dès lors les instructions atomiques peuvent être distribuées sur n'importe quel site. Il y a juste une petite exception: imaginons une instruction séquentielle qui appelle une \texttt{METHOD}. Si cette \texttt{METHOD} peut également être appelée depuis un \texttt{WHEN}, et qu'il n'y a pas de contraintes sur ce \texttt{WHEN}, ce \texttt{WHEN} et cette \texttt{METHOD}, qui forment un bloc atomique, ne peuvent pas être distribués sur n'importe quel site. En effet, l'exécution de la méthode doit être synchronisée puisqu'elle peut être appelée depuis la \texttt{SEQUENCE}. Cependant, les instructions de cette \texttt{METHOD} et de ce \texttt{WHEN} n'ont pas besoin de se trouver dans le graphe, mais recevront la même couleur que celle de l'instruction d'appel de cette \texttt{METHOD}. \\

La seconde, c'est que les arcs sont pondérés, afin de pouvoir calculer le coût de transmission. Ces pondérations se font de la même manière que dans le graphe de contrôle séquentiel, défini en section~\ref{distrib_algo_second_step}. \\

Les n\oe{}uds de ce graphe auront également des attributs. Chaque n\oe{}ud aura donc un attribut ``ancienne couleur'', et un autre ``nouvelle couleur'' qui permettront de calculer les deux coûts. Nous verrons, plus loin, comment ces attributs sont initialisés ainsi que leur importance dans le calcul des coûts. Et comme une image vaut mille mots, une figure représentant ce type de graphe, sur l'exemple de la figure~\ref{compare_graph_ex}, est représentée en figure~\ref{recolor_graph_ex}. \\

\begin{figure}[h]
	\begin{center}
		\includegraphics[scale=0.4]{Images/recolor_graph_ex.pdf}
		\caption{Le graphe pour la re-coloration, basé sur le morceau de code de la figure~\ref{compare_graph_ex}}
		\label{recolor_graph_ex}
	\end{center}
\end{figure}

\subsection{Modélisation des coûts}
\label{opti-color-def}

Les coûts sont utilisés pour essayer d'avoir une coloration qui a le bon compromis entre la conservation de la structure de distribution et le nombre de messages à envoyer. Ces coûts seront calculés à partir du second graphe que nous avons vu ci-dessus, le graphe pour le problème de la re-coloration. Nous allons donc voir comment ces coûts pourraient être calculés à partir de ce graphe. Les explications données ici sont purement intuitives et informelles. Une formalisation sera faite en même temps que la modélisation formelle du problème de re-coloration, en section~\ref{prob-decision}.

\subsubsection{Calcul du coût de re-coloration}

Le coût de re-coloration, équivalent au coût de redistribution défini dans la section~\ref{sect-crit-opti}, est égal, intuitivement, au nombre de n\oe{}uds qui changent de couleur. C'est ici que les attributs du graphe de re-coloration entrent en jeu. En effet, le coût est une sommation sur le nombre de n\oe{}uds qui ont une ancienne couleur différente de leur nouvelle couleur. Précisons maintenant quelles anciennes couleurs on assigne aux n\oe{}uds: \\

\begin{description}
	\item[Pour un n\oe{}ud non modifié,]c'est-à-dire qui est une image de la fonction $M$, son ancienne couleur est la même que celle du n\oe{}ud auquel il correspond. 
	
	\item[Pour un n\oe{}ud ajouté ou modifié,]comme ce n'est pas une image de la fonction $M$, son ancienne couleur est une couleur spéciale: le blanc. Cette couleur est spéciale pour deux raisons: (i) elle ne sera jamais assignée à un n\oe{}ud en tant que nouvelle couleur finale, et (ii) le fait d'assigner une nouvelle couleur, alors que l'ancienne est le blanc, ne fait pas augmenter le coût de re-coloration.
	
	\item[Pour un n\oe{}ud qui a une contrainte,]peu importe qu'il ait été modifié ou non, son ancienne couleur sera la couleur de sa contrainte actuelle (qui peut être la même que l'ancienne ou une nouvelle). Ceci permet de ne pas faire augmenter le coût de re-coloration puisque nous savons que la nouvelle couleur sera celle de la contrainte.
\end{description}

Nous pouvons facilement nous apercevoir que les trois cas cités ci-dessus couvrent bien tous les types de n\oe{}uds qu'on pourrait avoir. En effet, dès qu'un n\oe{}ud a une contrainte, il rentre dans le troisième cas, qu'il ait été modifié ou non. Un n\oe{}ud qui n'a plus sa contrainte rentrera dans le premier ou le second cas, dépendant du fait qu'il ait été modifié ou non. Maintenant, voyons les différents cas possibles pour l'assignation de la nouvelle couleur et quand cette assignation augmente effectivement le coût de re-coloration: \\

\begin{description}
	\item[L'ancienne couleur était le blanc:]dans ce cas, l'assignation d'une nouvelle couleur (qui ne peut évidemment pas être le blanc) ne fait pas augmenter le coût de re-coloration. En effet, comme ce n\oe{}ud n'avait pas de couleur, il fallait de toutes façons lui en assigner une, c'est pourquoi nous ne considérons pas ceci comme une re-coloration.
	
	\item[La nouvelle couleur est la même que l'ancienne:]dans ce cas, le coût n'augmente pas puisque les couleurs sont conservées et, par conséquent, la structure de distribution également.
	
	\item[La nouvelle couleur est différente de l'ancienne:]dans ce cas, le coût augmente. En effet, son ancienne couleur n'étant pas le blanc (sinon on se serait retrouvé dans le premier cas), la structure a donc été modifiée, ce qui résulte d'une augmentation du coût.
	
	\item[Le n\oe{}ud a une contrainte:]dans ce cas, nous ne considérons pas que le coût augmente puisque nous n'avons pas le choix de la nouvelle couleur qui est imposée par la contrainte.
\end{description}

\bigskip
Pour résumer l'idée du coût de re-coloration, celui-ci n'augmente que lorsque la structure est effectivement modifiée, c'est-à-dire lorsque un n\oe{}ud non-modifié et sans contraintes change de couleur par rapport à l'ancienne.

\subsubsection{Calcul du coût de transmission}
Intuitivement, le calcul du coût de transmission revient à additionner les poids des arcs entre deux n\oe{}uds dont les nouvelles couleurs sont différentes. Dès lors, pour faire diminuer le coût de transmission, il faudra essayer de mettre les mêmes nouvelles couleurs aux n\oe{}uds qui sont reliés par un arc. Bien sûr, dans certains cas, ceci ne sera pas possible. En effet, si les deux ont des contraintes différentes, aucun changement ne pourra être effectué. \\

La contradiction entre les deux coûts s'illustre bien ici: pour diminuer le coût de transmission, il faut modifier les nouvelles couleurs de certains n\oe{}uds. Si ces n\oe{}uds n'ont pas de contraintes et ont une ancienne couleur différente du blanc, le coût de re-coloration augmentera puisque nous changeons la structure de distribution.

\subsection{Problème de la comparaison de graphes}
\label{prob-comp-graph}

Le problème de comparaison de graphes nous sert à détecter les n\oe{}uds inchangés entre les deux graphes. Cette détection sera utile pour pré-colorer le nouveau graphe, en conservant les anciennes couleurs des n\oe{}uds non-modifiés (cela représente le désir de conservation de la structure de distribution). Le but de ce problème est donc de trouver une fonction de \textit{matching} entre les n\oe{}uds de l'ancien et ceux du nouveau graphe. \\

Le problème de comparaison de graphes est un problème très intéressant et dont les applications sont multiples dans une multitude de branches de la science pour la reconnaissance de motifs (comparaison ADN, reconnaissance d'objets sur des images, etc.). En théorie informatique, ce problème a été étudié de plusieurs manières, par différentes modélisations, telles que l'isomorphisme de graphes, l'isomorphisme de sous-graphes, la détection du sous-graphe commun maximum entre deux graphe ou encore la correspondance de graphes par correction d'erreurs. Pour notre problème de comparaison, il serait intéressant d'explorer toutes ces notions pour déceler celle qui colle le plus à notre problème, dans le but de résoudre celui-ci. Les définitions données ci-dessous viennent de plusieurs articles, tels que~\cite{SubGrIsoAlgo}, \cite{GrMaThAlAp}, \cite{MCSAlgoComp}, \cite{AlgoInexactMatch} et \cite{GrIsomProb}.

\begin{definition}{Isomorphisme de graphes}
	Soient deux graphes, $G_1 = (V_1, E_1, \alpha_1, \beta_1)$ et $G_2 = (V_2, E_2, \alpha_2, \beta_2)$, avec $V_1$ l'ensemble des n\oe{}uds, $E_1$ l'ensemble des arcs, $\alpha_1$ une fonction d'assignation de label aux n\oe{}uds et $\beta_1$ une fonction d'assignation de label aux arcs (les définitions sont les mêmes pour $G_2$). Un isomorphisme de graphes entre $G_1$ et $G_2$ est une fonction bijective $f: V_1 \rightarrow V_2$ telle que 
	\begin{itemize}
		\item $\alpha_1(v) = \alpha_2(f(v)) \; \forall v \in V_1$
		\item Pour chaque arc $e = (u, v) \in E_1$, il existe un arc $e' = (f(u), f(v)) \in E_2$ tel que $\beta_1(e) = \beta_2(e')$, et pour chaque arc $e' = (u', v')$, il existe un arc $e = (f^{-1}(u'), f^{-1}(v'))$ tel que $\beta_1(e) = \beta_2(e')$.
	\end{itemize}
\end{definition}

\begin{definition}{Sous-graphe}
	Un sous-graphe d'un graphe $G$ est un graphe dont l'ensemble des n\oe{}uds est un sous-ensemble des n\oe{}uds de $G$ et dont la relation d'adjacence est un sous-ensemble de celle de $G$.
\end{definition}

\begin{definition}{Isomorphisme de sous-graphes}
	Soient deux graphes, $G_1 = (V_1, E_1)$ et $G_2 = (V_2, E_2)$. Un isomorphisme entre $G_1$ et un sous-graphe de $G_2$ est appelé isomorphisme de sous-graphe.
\end{definition}

\begin{definition}{Distance d'édition entre deux graphes}
	Soient deux graphes $G_1 = (V_1, E_1)$ et $G_2 = (V_2, E_2)$. La distance d'édition entre $G_1$ et $G_2$ est le nombre minimum d'opérations sur les graphes (telles que l'ajout, la suppression ou l'édition de n\oe{}uds ou d'arcs) requises pour transformer $G_1$ en $G_2$. 
\end{definition}

\begin{definition}{Correspondance de graphes par correction d'erreurs}
	Soient deux graphes, $G_1 = (V_1, E_1)$ et $G_2 = (V_2, E_2)$.  Une correspondance de graphes par correction d'erreurs est une transformation de $G_1$ à l'aide d'opérations sur les graphes telles que l'ajout, la suppression ou l'édition de n\oe{}uds ou d'arcs afin d'obtenir le graphe $G_2$.
\end{definition}

\begin{definition}{Sous-graphe commun}
	Soient deux graphes, $G_1$ et $G_2$, un sous-graphe commun de $G_1$ et $G_2$ est un graphe $G'$ tel qu'il existe un isomorphisme de sous-graphe entre $G'$ et $G_1$ et il existe un isomorphisme de sous-graphe entre $G'$ et $G_2$. 
\end{definition}

\begin{definition}{Sous-graphe commun maximum}
	Soient deux graphes, $G_1$ et $G_2$, $G'$ est un sous-graphe commun maximum de $G_1$ et $G_2$, noté $MCS(G_1, G_2)$, s'il n'existe aucun autre sous-graphe commun de $G_1$ et $G_2$ dont le nombre de n\oe{}uds est strictement supérieur à celui de $G'$.
\end{definition}

\noindent
Détaillons un peu plus les définitions ci-dessus et donnons des complexités aux problèmes associés à ces notions.

\begin{description}
	\item[L'isomorphisme de graphes] est un problème bien connu et très populaire dans la littérature scientifique puisqu'il est très utile (on peut trouver une pléthore d'applications, comme la reconnaissance d'objets sur une image) et qu'il est l'un des rares problèmes dont on sait qu'ils appartiennent à la classe de complexité NP, sans savoir s'ils appartiennent à l'un des sous-ensembles bien connus de NP: P ou NP-complet. Une classe a d'ailleurs spécialement été définie pour le problème d'isomorphisme de graphe. Elle se trouve dans NP et est nommée \textsl{GI}, de la même manière que le problème (\textit{Graph Isomorphism}).
	
	\item[L'isomorphisme de sous-graphes] est la généralisation du problème précédent. En effet, il est bien connu qu'un sous-ensemble d'un ensemble $A$ peut être l'ensemble $A$ lui-même. Ce qui veut dire qu'un isomorphisme entre un graphe $G_2$ et un sous-graphe $G'_1$ de $G_1$ peut être un isomorphisme de graphes, dans le cas ou l'ensemble des n\oe{}uds de $G'_1$ est le même que celui de $G_1$ et la relation d'adjacence de $G'_1$ est la même que celle de $G_1$. Contrairement à son cas particulier, l'isomorphisme de sous-graphes est connu comme un problème NP-complet.
	
	\item[La correspondance de graphes par correction d'erreurs] est un problème d'isomorphisme abordé différemment. Il fait partie d'une catégorie de \textsl{matching} inexact qui ne sera pas couvert dans ce mémoire. Ce problème est, encore une fois, NP-complet et on peut s'en rendre compte en imaginant qu'il faut essayer toutes les combinaisons de modifications sur un graphe pour tenter d'obtenir le second.
	
	\item[La détection d'un sous-graphe commun maximum] est encore une autre manière de voir le problème d'isomorphisme. Il ne faut pas, ici, se soucier de savoir quel graphe est le sous-graphe de l'autre pour connaître le sens de l'isomorphisme: il s'agit seulement de créer un troisième graphe qui sera (isomorphe à) un sous-graphe des deux autres. Le problème associé, celui de trouver le plus grand des sous-graphes communs, est connu comme étant NP-complet~\cite{MRG-DSJ}. 
\end{description}

\bigskip
Ainsi, tous les problèmes connus qui auraient pu aider à formaliser le problème de comparaison traité ici n'ont pas de solutions efficace au pire cas. Encore reste-t-il à montrer qu'au moins un de ces problèmes correspond à notre problème de comparaison. La correspondance de graphes par correction d'erreurs aurait pu être une piste, mais nous l'avons écarté volontairement de notre recherche. La raison est qu'il n'est pas meilleur en complexité (NP-complet également) et qu'il est nécessaire de travailler sur l'ensemble des noeuds et l'ensemble des arcs, or nous n'avons besoin de savoir que les similitudes entre les noeuds. Dans la suite, nous allons d'abord montrer que l'isomorphisme de (sous-)graphes ne correspond pas à notre problème. Ensuite, nous montrons que la détection d'un sous-graphe commun maximum l'est, et c'est donc sur ce problème que nous allons nous baser pour trouver une solution à notre problème de comparaison.

\subsubsection{La non-équivalence entre le problème d'isomorphisme de sous-graphes et notre problème de comparaison}
Le but de notre problème est de trouver un \textit{mapping} entre les n\oe{}uds de l'ancien graphe et les n\oe{}uds du nouveau graphe. De façon similaire, le but de l'isomorphisme de sous-graphes est de trouver un \textit{mapping} entre les n\oe{}uds d'un premier graphe et les n\oe{}uds d'un sous-graphe d'un second graphe. Jusque là, les deux problèmes peuvent paraître similaires, mais une observation plus précise montrera que l'isomorphisme de sous-graphes ne peut pas correspondre à notre problème de comparaison et, donc, qu'une solution au problème d'isomorphisme ne peut pas être utilisée pour résoudre notre problème. \\

En fait, ce qui fait que les deux problèmes ne peuvent pas correspondre est que, dans notre problème de comparaison, les deux graphes peuvent ne pas être des sous-graphes l'un de l'autre. En effet, au vu des modifications que l'on peut apporter, définies dans la section~\ref{modif-code-possible}, il est possible qu'avec une combinaison d'ajouts et de suppressions de n\oe{}uds, aucun des deux graphes ne puisse être le sous-graphe de l'autre. Imaginons un graphe $G_1$ duquel on supprime un n\oe{}ud et on en rajoute un autre, le graphe $G_2$ résultant ne contient pas de sous-graphe qui puisse être isomorphe à $G_1$. De même, le graphe $G_1$ ne peut pas contenir un sous-graphe isomorphe à $G_2$ à cause du n\oe{}ud présent dans $G_1$ et qui a été supprimé. Par contre, on est capable de trouver un isomorphisme entre un sous-graphe de $G_1$ et un sous-graphe de $G_2$. 

\subsubsection{L'équivalence entre le problème de détection du sous-graphe commun maximum et notre problème de comparaison}
Nous allons, ici, montrer l'équivalence entre le problème de détection du sous-graphe commun maximum avec notre problème de comparaison, qui consiste à trouver l'ensemble des noeuds qui n'ont pas été modifiés entre deux versions d'un graphe. Montrer cette équivalence va nous permettre de pouvoir traiter notre problème comme un problème de détection du sous-graphe commun maximum et d'utiliser une solution existante de ce dernier, pour résoudre notre problème. \\

Au vu des modifications possibles, nous savons qu'il n'est pas possible de trouver un isomorphisme entre l'un des deux graphes et un sous-graphe de l'autre. Par contre, il serait possible de trouver une équivalence entre deux sous-graphes des deux graphes d'origine. En effet, dans notre problème de comparaison, il faut essayer de trouver tous les n\oe{}uds qui n'ont pas été modifiés entre l'ancien graphe et le nouveau. Ceci revient à chercher le plus grand ensemble de paires de n\oe{}uds (une paire contient un n\oe{}ud de l'ancien et un n\oe{}ud du nouveau graphe) qui montre les équivalences entre les n\oe{}uds. Si nous arrivons à montrer que la recherche du plus grand sous-graphe commun entre deux graphes revient à chercher cet ensemble de paires de n\oe{}uds, cela signifierait que les deux problèmes correspondent et, par conséquent, que s'il existe une solution pour le problème de détection de sous-graphe commun maximum, cette solution pourrait être adaptée à notre problème de comparaison. \\

La détection d'un sous-graphe commun maximum entre deux graphes revient à construire un sous-graphe commun jusqu'à ce qu'on ne puisse plus ajouter de n\oe{}uds. Nous pouvons représenter la construction d'un tel sous-graphe à l'aide d'états. L'état initial étant le graphe vide (qui est, par définition des ensembles, un sous-graphe commun) et le passage d'un état à un autre se fait en ajoutant un n\oe{}ud qui se retrouve à la fois dans les deux graphes. Dès lors, si nous décidons de construire un graphe tel que chaque n\oe{}ud est, en fait, une paire contenant les deux n\oe{}uds équivalents dans les deux graphes et les arcs sont ceux de la nouvelle version du graphe que l'on compare, lorsqu'il n'y aura plus de paires possibles à ajouter, le sous-graphe commun maximum sera trouvé. Son ensemble de n\oe{}uds sera un ensemble de paires de n\oe{}uds, soit l'ensemble recherché pour notre problème de comparaison. Nous considérons également qu'il n'est pas possible de se tromper lorsqu'on fait correspondre deux n\oe{}uds entre eux, ceci grâce à des attributs que l'on ajoute aux n\oe{}uds pour les rendre uniquement identifiables (nous expliquerons ces attributs plus loin dans ce travail). \\

Notre problème de comparaison, rappelons-le, consiste à trouver, entre deux versions d'un graphe, le plus grand ensemble de n\oe{}uds qui n'ont pas été modifiés. Dès lors, si nous construisons un ensemble de paires de n\oe{}uds (un n\oe{}ud de chaque version du graphe) et que nous considérons chaque paire comme un n\oe{}ud, nous avons un ensemble de n\oe{}uds. Il ne reste plus qu'à définir les arcs pour obtenir un graphe et montrer que c'est bien un sous-graphe commun maximum. Nommons $G_1=(V_1, E_1)$ et $G_2=(V_2, E_2)$, respectivement l'ancienne et la nouvelle version du graphe que l'on compare et $G_3=(V_3, E_3)$ le graphe que nous tentons de construire. Nous ajoutons un arc dans $E_3$ entre $(n_1, n_2) \in V_3$ et $(n'_1, n'_2) \in V_3$ tel qu'il existe un arc entre $n_2$ et $n'_2$ dans $E_2$. En clair, les arcs de $G_3$ sont les mêmes arcs que $G_2$, pour les n\oe{}uds qui sont repris dans $G_3$. L'ensemble des n\oe{}uds de $G_3$ est bien un sous-ensemble des n\oe{}uds de $G_1$ et, également, un sous-ensemble des n\oe{}uds de $G_2$. L'ensemble des arcs de $G_3$ est, par construction, un sous-ensemble des arcs de $G_2$ et c'est également un sous-ensemble des arcs de $G_1$ puisque, si les noeuds n'ont pas été modifiés, par définition des arcs des graphes que l'on compare, les arcs de $G_3$ sont également des arcs de $G_1$. \\

Nous venons de montrer une équivalence entre notre problème de comparaison et le problème de détection de sous-graphe commun maximum entre deux graphes. Ceci nous permet de déduire deux choses : (i) notre problème ne peut pas avoir de solution polynomiale au pire cas (à moins que $P = NP$), et (ii) si une solution existe pour le problème de détection de sous-graphe commun maximum, cette solution peut être utilisée pour notre problème de comparaison. Il reste encore à argumenter le fait que nous recherchons le plus grand ensemble de noeuds qui n'ont pas été modifiés. Le but de cette comparaison est de pouvoir trouver les noeuds qui pourront reprendre leur ancienne couleur, ce qui nous permettra d'avoir une coloration plus rapide sur les noeuds. \\

Même si, théoriquement, nous venons de montrer qu'aucune solution polynomiale ne peut être trouvée pour notre problème, il sera, toutefois, possible, en pratique, d'en trouver une. En effet, il est possible de simplifier grandement le problème en retirant certains n\oe{}uds dont on sait qu'il ne faut pas les comparer (ceci sera expliqué en détail dans la section~\ref{solution_compare_graphs}). Également, en pratique, les n\oe{}uds ont des attributs (comme décrits en section~\ref{graph-definition}), ce qui va permettre de les rendre unique et de résoudre, en grande partie, le problème. Une solution, basée sur un algorithme de détection de sous-graphe commun, sera donnée en section~\ref{solution_compare_graphs}, juste après la description des simplifications à effectuer. 

\subsection{Problème de la recherche d'une re-coloration optimale}
\label{prob-decision}

Supposons que nous avons un résultat au problème précédent, c'est-à-dire un \textit{mapping} entre les n\oe{}uds du graphe avant la modification et les n\oe{}uds du graphe après la modification. Tous les n\oe{}uds du graphe après modification qui ne se trouvent pas dans le \textit{mapping} sont donc des n\oe{}uds ajoutés ou modifiés. Le principe est alors de trouver une manière de colorer le nouveau graphe tout en gardant les propriétés d'optimalité demandées, à savoir : (i) une structure de distribution la plus proche possible de l'ancienne structure, et (ii) un minimum de transmissions de messages. Il s'agit, comme nous l'avons déjà mentionné, d'un compromis entre ces deux critères. Dès lors, un programmeur peut vouloir donner plus d'importance à l'un des deux coûts, c'est pourquoi nous ajoutons des paramètres dans l'équation d'optimalité de la re-coloration, qui est la suivante: 
\begin{equation*}
	O_d = min(\alpha C_r + \beta C_t)
\end{equation*}
avec $C_r$ qui représente le coût de re-coloration (critère de conservation de la structure de distribution) et $C_t$ qui représente le coût de transmission (critère de minimisation des transmissions). Le fait de multiplier $\alpha$ à $C_r$ et $\beta$ à $C_t$ modélise bien l'importance qu'on donne aux deux coûts. En effet, si nous prenons un $\alpha$ égal au $\beta$, les deux coûts auront la même importance dans l'équation: si l'un augmente d'une unité et que l'autre diminue de une unité, le coût total n'aura pas changé. En revanche, si nous prenons un $\beta$ deux fois supérieur à $\alpha$, le second coût aura deux fois plus d'importance. En effet, si $C_t$ augmente de $1$ et $C_r$ diminue de $1$, le coût total aura quand même augmenté parce que $C_t$ a plus d'importance. Nous avons donné, en section~\ref{opti-color-def}, une idée intuitive des calculs de ces deux coûts et c'est dans cette section que nous allons donner une définition plus formelle pour ces deux coûts. \\

Avant de commencer le problème de re-coloration, nous colorons les n\oe{}uds sur lesquels des contraintes de couleur sont appliquées, ainsi que les n\oe{}uds qui sont dans le \textit{mapping} donné par le problème précédent. Ce qui nous intéresse ici, c'est de réduire le coût de transmission, puisque le coût de re-coloration est déjà à son minimum. En effet, comme nous avons déjà coloré les n\oe{}uds qui sont dans le \textit{mapping}, cela signifie que nous avons conservé la structure de distribution d'avant. Le graphe permettant de traiter le coût de transmission a été défini en section~\ref{graph-definition} et celui-ci ne contient pas tous les n\oe{}uds. Certains n\oe{}uds qui ne sont pas dans ce graphe n'ont pas encore de couleur. Cependant, comme ils ne sont pas dans ce graphe, leur couleur n'influe pas sur le coût de transmission et, par conséquent, nous pouvons leur donner n'importe quelle couleur. À ce stade donc, il ne reste plus que quelques n\oe{}uds du graphe défini pour le problème de re-coloration à colorer. Nous pouvons, dès lors, donner une définition formelle du calcul des coûts et modéliser formellement le problème de re-coloration sur base de ce graphe. \\

Soit un graphe pour la re-coloration $G = (V, E)$ tel que $V$ est l'ensemble des n\oe{}uds et $E$ est l'ensemble des arcs. Soient $S = (s_1, s_2, ..., s_K)$ un ensemble d'ensembles disjoints de n\oe{}uds, $C$ un ensemble de couleurs ($|C| = m$) et $D = (d_1, d_2, ..., d_m)$ un ensemble d'ensembles de n\oe{}uds contraints (tel que si $n \in d_i$, $n$ doit avoir la couleur $c_i \in C$). Soient, également, $c$ et $c'$ qui sont, respectivement, les attributs ``ancienne couleur'' et ``nouvelle couleur''. Le problème est donc de trouver une coloration finale, c'est-à-dire d'assigner une couleur aux $c'$ de tous les n\oe{}uds, de telle manière que cette coloration minimise \\

\begin{equation*}
	min(\alpha C_r + \beta C_t)
\end{equation*}
où
\begin{align*}
	& C_r = \sum_{n \in V} C_{r_n} \\
	& C_t = \sum_{e \in E} C_{t_e}
\end{align*}
en respectant les deux contraintes suivantes: 
\begin{align*}
	& (1) \; \forall j, 1 \leq j \leq K: \forall a,b \in s_j : a.c' = b.c' \\
	& (2) \; \forall i, 1 \leq i \leq m: \forall a \in d_i : a.c' = c_i \; (c_i \in C)
\end{align*}
Il reste encore à définir formellement le calcul des $C_{r_n}$ et des $C_{t_e}$:
\begin{align}
	\label{formula:crn}
	\forall n \in V: C_{r_n} = 
	& \begin{cases}
		1 \text{ si }c_n \neq c'_n \wedge c_n \neq blanc \\
		0 \text{ sinon.}
	\end{cases}
	\\
	\label{formula:cte}
	\forall e = (a, b, p) \in E: C_{t_e} = 
	& \begin{cases}
		p \text{ si } c'_a \neq c'_b \\
		0 \text{ sinon.}
	\end{cases}
\end{align}

L'équation~(\ref{formula:crn}) modélise correctement le fait que si un n\oe{}ud change de couleur (son ancienne et sa nouvelle couleur sont différentes) et que son ancienne n'est pas le blanc, le coût de re-coloration pour ce n\oe{}ud est de 1. En effet, nous l'avons dit, un tel cas représente un changement de structure de distribution. Dans les autres cas, le coût de re-coloration est bien égal à 0. \\

L'équation~(\ref{formula:cte}) augmente le coût de transmission de $p$ ($p > 0$) si l'arc relie deux n\oe{}uds dont les couleurs sont différentes. En effet, comme les couleurs sont différentes, il faut un message de synchronisation entre les deux et, par conséquent, on doit augmenter le coût de transmission. \\

Les intuitions que nous avons données avant sont donc bien retranscrites par les deux équations ci-dessus. Maintenant, afin d'éviter d'avoir des conditions pour les $C_{r_n}$ et $C_{t_e}$, modifions quelque peu la modélisation du problème. Soit la variable $X_{n_c}$ qui représente la nouvelle couleur de n (c'est donc l'équivalent de l'attribut $c'$ de $n$) et qui est définie comme suit:
\begin{align*}
	X_{n_c} = 
	\begin{cases}
		1 \text{ si $n \in V$ a la couleur $c$} \\
		0 \text{ sinon.}
	\end{cases}
\end{align*}
Nous pouvons exprimer le problème d'optimisation de la manière suivante (on suppose toujours les $p > 0$):  
\begin{equation}
	\label{equation_min}
	min \left(\alpha \sum_{n \in V: c_n \neq blanc} (1 - X_{n_{c_n}}) + \beta \sum_{e = (a, b, p) \in E} p Y_e\right)
\end{equation} 
\begin{align*}
	\text{Sous les contraintes}
	\begin{cases}
		\sum_{c \in C} X_{n_c} = 1 \; (\forall n \in V) \\
		Y_e \geq | X_{a_c} - X_{b_c} | \; (\forall c \in C) \\
		X_{a_c} = X_{b_c} \; (\forall j, 1 \leq j \leq K,  \forall a, b \in s_j, \forall c \in C) \\
		X_{a_{c_i}} = 1 \; (\forall a \in d_i, 1 \leq i \leq m)
	\end{cases}
\end{align*}
Quelques explications sont cependant nécessaires.\\

Le coût $C_r$ a été remplacé par la première somme dans l'équation~(\ref{equation_min}). Cette somme est effectuée sur tous les n\oe{}uds du graphe, à l'exception des n\oe{}uds dont l'ancienne couleur est blanche, c'est-à-dire les n\oe{}uds ajoutés ou modifiés (puisque nous avons dit que ces n\oe{}uds-là n'augmentent pas le coût puisqu'il faut, de toute façon, leur assigner une couleur). Le terme $X_{n_{c_n}}$ revient à se demander si le n\oe{}ud $n$ a, comme nouvelle couleur, la couleur $c_n$, c'est-à-dire son ancienne couleur. En d'autres termes, $(1 - X_{n_{c_n}})$ vaudra $0$ si la couleur n'a pas changé (puisque $X_{n_{c_n}}$ vaudra 1), et il vaudra $1$ si elle a changé (puisque $X_{n_{c_n}}$ vaudra 0). Ce qui modélise correctement $C_r$. \\ 

Le coût $C_t$, lui, a été remplacé par la seconde somme de l'équation~(\ref{equation_min}).  Cette somme est effectuée sur tous les arcs du graphe et le terme de la somme est: $p Y_e$. Le facteur $p$ est le poids de l'arc en question, tandis que $Y_e$ est défini comme $ \max_{c \in C} |X_{a_c} - X_{b_c}|$. C'est-à-dire qu'il est défini par rapport aux couleurs de ces extrémités. Deux cas peuvent alors arriver: 

\begin{enumerate}
	\item Les couleurs de $a$ et $b$ sont les mêmes, donc le terme $Y_e$ vaudra $0$ puisque, pour chaque couleur, on aura $|0 - 0|$ sauf pour la couleur de $a$ et $b$ où on aura $|1 - 1|$, ce qui sera égal à $0$.
	
	\item Les couleurs de $a$ et $b$ sont différentes, donc le terme $Y_e$ vaudra $1$. En effet, si $c$ est la couleur de $a$ et $c'$ est la couleur de $b$ ($c \neq c'$), pour toutes les couleurs exceptés $c$ et $c'$, on aura $|0 - 0|$. Pour la couleur $c$, on aura $|1 - 0|$ et pour la couleur $c'$, on aura $|0 - 1|$. Le max de ces termes sera donc $1$.
\end{enumerate}
Le coût de transmission est donc correctement modélisé: soit les deux extrémités d'un arc ont des couleurs identiques et le coût n'augmente pas (le premier cas, ci-dessus), soit les deux extrémités ont d'un arc ont des couleurs différentes et le coût augmente de $1*p$ (le second cas ci-dessus). \\

En ce qui concerne les contraintes, la première impose que les n\oe{}uds n'ont qu'une et une seule couleur. La seconde définit $Y_e$. La troisième impose que les n\oe{}uds qui se trouvent dans un même ensemble $s_j \in S$ soient de la même couleur, ce qui représente les n\oe{}uds qui sont reliés entre eux. Enfin, la quatrième contrainte modélise le fait qu'un n\oe{}ud sur lequel une contrainte est imposée ne peut pas avoir d'autre couleur que la couleur $c_i$. \\

Une petite simplification peut être apportée à cette modélisation. En effet, il est possible de ne considérer que les arcs entre les ensembles $s_k \in S$ et, ainsi, d'enlever la troisième contrainte ci-dessus. La modélisation devient alors: soit $k(i)$ : $k$ tel que $i \in s_k$ ($1 \leq k \leq K$), $X_{k_c}$ défini comme suit: 
\begin{align*}
	X_{k_c} = 
	\begin{cases}
		1 \text{ si tous les n\oe{}uds de $s_k$ ont la couleur c} \\
		0 \text{ sinon.}
	\end{cases}
\end{align*}
et $Y_e$ défini comme suit: 
\begin{align*}
	Y_e = 
	\begin{cases}
		1 \text{ si les extrémités de $e$ sont de couleur différente} \\
		0 \text{ sinon.}
	\end{cases}
\end{align*}
L'équation~\ref{equation_min} peut être écrite de la manière suivante: 
\begin{equation}
	\label{equation_min_2}
	min (\alpha \sum_{n \in V: c_n \neq blanc} (1 - X_{k(n)_{c_n}}) + \beta \sum_{e = (a, b, p_e) \in E} p_e Y_e)
\end{equation}
\begin{align*}
	\text{Sous les contraintes}
	\begin{cases}
		\sum_{c \in C} X_{k_c} = 1 \; (1 \leq k \leq K) \\
		Y_e \geq | X_{k(a)_c} - X_{k(b)_c} | \; (\forall c \in C) \\
		X_{k(a)_{c_i}} = 1 \; (\forall a \in d_i, 1 \leq i \leq m)
	\end{cases}
\end{align*}

Le terme $X_{k(a)_c}$ désigne donc la couleur du n\oe{}ud $a$, étant donné que $k(a)$ est défini comme étant le $k$ tel que le n\oe{}ud $a$ appartient à $s_k$. Le reste des équations ne nécessite pas d'explications supplémentaires, puisqu'il s'agit d'une simple ré-écriture des formules avant la simplification. \\


Nous verrons, dans la section~\ref{solution_opti_coloration}, quel algorithme peut être utilisé pour résoudre un tel problème d'optimisation. Ceci clôture la section dédiée à la modélisation formelle des deux problèmes composant le problème initial. 